We investigate an optimal scheduling problem in a discrete-time system of Lparallel queues that are served by K identical, randomly connected servers.Each queue may be connected to a subset of the K servers during any given timeslot. This model has been widely used in studies of emerging 3G/4G wirelesssystems. We introduce the class of Most Balancing (MB) policies and providetheir mathematical characterization. We prove that MB policies are optimal; wedefine optimality as minimization, in stochastic ordering sense, of a range ofcost functions of the queue lengths, including the process of total number ofpackets in the system. We use stochastic coupling arguments for our proof. Weintroduce the Least Connected Server First/Longest Connected Queue (LCSF/LCQ)policy as an easy-to-implement approximation of MB policies. We conduct asimulation study to compare the performance of several policies. The simulationresults show that: (a) in all cases, LCSF/LCQ approximations to the MB policiesoutperform the other policies, (b) randomized policies perform fairly close tothe optimal one, and, (c) the performance advantage of the optimal policy overthe other simulated policies increases as the channel connectivity probabilitydecreases and as the number of servers in the system increases.
展开▼
